package leetcode_700;

/**
 *@author 周杨
 *ValidParenthesisString_678 括号表达式的匹配 *可以匹配任何( )和空格 问是否是合法的表达式
 *describe:用回溯 AC 27%
 *2018年10月6日 下午4:14:09
 */
public class ValidParenthesisString_678 {
	public boolean checkValidString(String s) {
		if(s.length()==0)
			return true;
        char chars[]=s.toCharArray();
        return help(chars,0,0);
    }

	private boolean help(char[] chars, int index, int left) {
		if(index==chars.length)
			return left==0?true:false;
		if(chars[index]=='(') {
			if(left+2>chars.length-index) {//剩下所有的都无法匹配(了
				return false;
			}
			return help(chars,index+1,left+1);
		}
		else if(chars[index]==')') {
			if(left==0)
				return false;
			return help(chars,index+1,left-1);
		}
		else {
			boolean flag=help(chars,index+1,left);//当空格来处理
			if(flag)
				return true;
			flag=help(chars,index+1,left+1);
			if(flag)
				return true;
			if(left!=0) {
				return help(chars,index+1,left-1);
			}
		}
		return false;
	}
}
